package structure;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;

import java.util.NoSuchElementException;
import java.util.Objects;


/**
 * @author he peng
 * @create 2018/4/18 17:16
 * @see
 */

public class BinarySearchTree1<T extends Comparable<T>> {

    /*
        二叉查找树特性 ：
        1. 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
        2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
        3. 任意节点的左、右子树也分别为二叉查找树；
        4. 没有键值相等的节点。
     */

    private TreeNode<T> root;

    public boolean putVal(T val) {
        if (Objects.isNull(val)) {
            throw new IllegalArgumentException("val == null");
        }
        if (Objects.isNull(this.root)) {
            root = new TreeNode<>(null , null , null , val , 1L);
            return true;
        }
        TreeNode node = searchNode(this.root, val);
        int compareResult = node.getValue().compareTo(val);
        if (compareResult == 0) {
            node.setValue(val);
        } else if (compareResult > 0) {
            // go left
            node.setLeft(new TreeNode(node , null , null , val , 1L));
            node.size++;
        } else {
            // go right
            node.setRight(new TreeNode(node , null , null , val , 1L));
            node.size++;
        }
        if (! Objects.equals(this.root, node)) {
            this.root.size = size() + 1;
        }
        return true;
    }

    public long size() {
        return size(this.root);
    }

    private long size(TreeNode node) {
        if (Objects.isNull(node)) {
            return 0;
        }
        return node.size;
    }


    public boolean isEmpty() {
        return size() == 0 ? true : false;
    }

    public void removeMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("tree is empty");
        }
        removeMax(this.root);
        System.out.println(this.root);
    }

    private void removeMax(TreeNode<T> node) {
        if (Objects.isNull(node)) {
            throw new IllegalArgumentException("node == null");
        }
        if (Objects.nonNull(node.right)) {
            removeMax(node.right);
        } else {
            if (Objects.nonNull(node.left)) {
                node.parent.right = node.left;
                node.left.parent = node.parent;
            } else {
                node.parent.right = null;
            }
            this.root.size = size() - 1;
        }
    }


    public void removeMin() {
        if (isEmpty()) {
            throw new NoSuchElementException("tree is empty");
        }
        removeMin(this.root);
        System.out.println(this.root);
    }

    private void removeMin(TreeNode<T> node) {
        if (Objects.isNull(node)) {
            throw new IllegalArgumentException("node == null");
        }
        if (Objects.nonNull(node.left)) {
            removeMin(node.left);
        } else {
            if (Objects.nonNull(node.right)) {
                node.right.parent = node.parent;
                node.parent.left = node.right;
            } else {
                node.parent.left = null;
            }
            this.root.size = size() - 1;
        }
    }

    public T floor(T val) {
        if (Objects.isNull(val)) {
            throw new IllegalArgumentException("val == null");
        }
        if (isEmpty()) {
            throw new NoSuchElementException("tree is empty");
        }
        return floor(this.root , val);
    }

    private T floor(TreeNode<T> node, T val) {
        if (Objects.isNull(node)) {
            return null;
        }
        int cmp = val.compareTo(node.value);
        if (cmp == 0) {
            return node.value;
        } else if (cmp < 0) {
            return floor(node.left , val);
        } else {
            T floor = floor(node.right, val);
            if (Objects.nonNull(floor)) {
                return floor;
            } else {
                return node.value;
            }
        }
    }

    public T ceiling(T val) {
        if (Objects.isNull(val)) {
            throw new IllegalArgumentException("val == null");
        }
        if (isEmpty()) {
            throw new NoSuchElementException("tree is empty");
        }
        return ceiling(this.root , val);
    }

    private T ceiling(TreeNode<T> node, T val) {
        if (Objects.isNull(node)) {
            return null;
        }
        int cmp = val.compareTo(node.value);
        if (cmp == 0) {
            return node.value;
        } else if (cmp > 0) {
            return ceiling(node.right , val);
        } else {
            T ceiling = ceiling(node.left, val);
            if (Objects.isNull(ceiling)) {
                return node.value;
            } else {
                return ceiling;
            }
        }
    }

    // TODO 还不理解
    public T select(int index) {
        if (index < 0 || index > size()) {
            throw new IllegalArgumentException("index invalid");
        }
        return select(this.root , index);
    }

    private T select(TreeNode<T> node, int index) {
        if (Objects.isNull(node)) {
            return null;
        }
        long size = size(node.left);
        if (size > index) {
            return select(node.left , index);
        } else if (size < index) {
            return select(node.right , index);
        } else {
            return node.value;
        }
    }

    public boolean remove(T val) {
        if (Objects.isNull(val)) {
            throw new IllegalArgumentException("val == null");
        }
        TreeNode node = searchNode(this.root, val);
        if (Objects.isNull(node)) {
            return true;
        }
        int cmp = node.getValue().compareTo(val);
        if (cmp == 0) {
            if (Objects.equals(this.root, node)) {
                if (Objects.isNull(this.root.getLeft()) && Objects.nonNull(this.root.getRight())) {

                }
            }
        } else if (cmp > 0) {
            node.setLeft(null);
        } else {
            node.setRight(null);
        }
        return true;
    }

    private TreeNode searchNode(TreeNode parentNode , T val) {
        if (Objects.isNull(parentNode)) {
            throw new IllegalArgumentException("parentNode == null");
        }
        int compareResult = parentNode.getValue().compareTo(val);
        if (compareResult == 0) {
            return parentNode;
        } else if (compareResult > 0) {
            // go left
            if (Objects.isNull(parentNode.getLeft())) {
                return parentNode;
            }
            return searchNode(parentNode.getLeft() , val);
        } else {
            // go right
            if (Objects.isNull(parentNode.getRight())) {
                return parentNode;
            }
            return searchNode(parentNode.getRight() , val);
        }
    }

    public void printTree() {

    }


    @AllArgsConstructor
    @Setter
    @Getter
    private static class TreeNode<T extends Comparable<T>> {
        BinarySearchTree1.TreeNode<T> parent;
        BinarySearchTree1.TreeNode<T> left;
        BinarySearchTree1.TreeNode<T> right;
        private T value;
        private Long size;
    }
}
